package leetcode.day_2020_11_23_11_29;

/**
 * 516. 最长回文子序列
 */
public class L_516 {
    public static void main(String[] args) {
        String s = "bbbab";
        System.out.println(longestPalindromeSubseq(s));
    }

    public static int longestPalindromeSubseq(String s) {
        int sLength = s.length();
        int[][] dp = new int[sLength][sLength];
        // 初始化
        for(int i=0; i<sLength; i++) {
            dp[i][i] = 1;
        }

        for(int i=sLength-1; i>=0; i--){
            for(int j=i+1; j<sLength; j++){
                if(s.charAt(i) == s.charAt(j)) {
                    dp[i][j] = dp[i+1][j-1]+2;
                }else {
                    dp[i][j] = Math.max(dp[i][j-1], dp[i+1][j]);
                }
            }
        }
        return dp[0][sLength-1];
    }
}
